`
https://leetcode.cn/problems/range-frequency-queries/
`

/**
 * @param {number[]} arr
 */
var RangeFreqQuery = function (arr) {
  // 保存每个数出现的索引位置，这样就是有序的，可以用二分快速查找
  this.idxs = arr.reduce((acc, cur, idx) => {
    if (!acc.has(cur)) acc.set(cur, [])
    const f = acc.get(cur)
    f.push(idx)
    return acc
  }, new Map())
};

/** 
 * @param {number} left 
 * @param {number} right 
 * @param {number} value
 * @return {number}
 */
RangeFreqQuery.prototype.query = function (left, right, value) {
  if (!this.idxs.has(value)) return 0
  const target = this.idxs.get(value)
  // 找左边界: >= left
  const leftBound = _.sortedIndex(target, left)
  // 找右边界: > right
  const rightBound = _.sortedIndex(target, right + 1)
  return rightBound - leftBound
};

/** 
 * Your RangeFreqQuery object will be instantiated and called as such:
 * var obj = new RangeFreqQuery(arr)
 * var param_1 = obj.query(left,right,value)
 */